#include <bits/stdc++.h>
using namespace std;
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using ll = long long;
const ll N=5e5+10;
ll p[N],n,m,zy[N],v[N],d[N];
vector<ll> g[N];
ll find(ll x)
{
    if(p[x]!=x)
    {
        return p[x] = find(p[x]);
    }
    return p[x];
}
ll dfs(ll st,ll ed)
{
    queue<ll> q;
    q.push(st);
    v[st]=1;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(auto& nt:g[now])
        {
            if(!v[nt])
            {
                if(now==st&&nt==ed)continue;
                v[now]=1;
                d[nt]=d[now]+1;
                q.push(nt);
            }
        }
    }
    return d[ed];
}
void solve()
{
    cin >> n >> m;
    ll l, r;
    for(ll i=1;i<=n;i++)
    {
        p[i] = i, zy[i] = 0, g[i].clear(),d[i]=0,v[i]=0;
    }
    for(ll i=1;i<=m;i++)
    {
        ll u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        ll fa = find(u), fb = find(v);
        if(fa==fb)
        {
            l = u, r = v;
            zy[fb]++;
        }
        else {
            p[fa] = fb;
            zy[fb] += zy[fa];
        }
    }

    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(p[i]==i&&zy[i]==1)
        {
            ans++;
        }
    }
    if(ans>=2||ans==0)
    {
        cout << "No " << ans << endl;
        return;
    }
    cout << "Yes ";
    ll cnt=dfs(l, r);
    cout << cnt+1 << endl;
}
int main()
{
    int t = 1;
    cin >> t;
    while(t--)
    {
        solve();
    }
   return 0;
}
